{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 单向链表的实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 单向链表的节点\n",
    "class ListNode(object):\n",
    "    def __init__(self, item):\n",
    "        self.val = item\n",
    "        self.next = None\n",
    "        \n",
    "    def __lt__(self, other):\n",
    "        return self.val < other.val\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        return self.val == other.val\n",
    "\n",
    "# 单向链表\n",
    "class SinglyLinkedList(object):\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        \n",
    "    def init_with_list(self, val_list):\n",
    "        if len(val_list) == 0:\n",
    "            return\n",
    "        self.head = ListNode(val_list[0])\n",
    "        x = self.head\n",
    "        for i in val_list[1:]:\n",
    "            x.next = ListNode(i)\n",
    "            x = x.next\n",
    "    \n",
    "    def get_node(self, index):\n",
    "        x = self.head\n",
    "        for i in range(index):\n",
    "            if not x:\n",
    "                return None\n",
    "            x = x.next\n",
    "        return x\n",
    "    \n",
    "    def get_length(self):\n",
    "        length = 0\n",
    "        x = self.head\n",
    "        while x:\n",
    "            x = x.next\n",
    "            length += 1\n",
    "        return length\n",
    "    \n",
    "    def append(self, item):\n",
    "        node = ListNode(item)\n",
    "        if self.head:\n",
    "            x = self.head\n",
    "            while x.next:\n",
    "                x = x.next\n",
    "            x.next = node\n",
    "        else:\n",
    "            self.head = node\n",
    "    \n",
    "    def insert_head(self, item):\n",
    "        x = ListNode(item)\n",
    "        x.next = self.head\n",
    "        self.head = x\n",
    "        \n",
    "    def to_list(self):\n",
    "        val_list = []\n",
    "        x = self.head\n",
    "        while x:\n",
    "            val_list.append(x.val)\n",
    "            x = x.next\n",
    "        return val_list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 206. 反转链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "反转一个单链表。\n",
    "\n",
    "示例:\n",
    "\n",
    "输入: 1->2->3->4->5->NULL\n",
    "输出: 5->4->3->2->1->NULL\n",
    "\n",
    "进阶:\n",
    "你可以迭代或递归地反转链表。你能否用两种方法解决这道题？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 用循环实现\n",
    "def reverse_list(head):\n",
    "    x = head\n",
    "    temp = None\n",
    "    while x:\n",
    "        n = x.next\n",
    "        x.next = temp\n",
    "        temp = x\n",
    "        x = n\n",
    "    return temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([])\n",
    "mylist.head = reverse_list(mylist.head)\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([1,2,3,4,5])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 4, 3, 2, 1]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.head = reverse_list(mylist.head)\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 用递归实现，在子链表中把尾部指针指向前一个元素\n",
    "def reverse_list2(head, pre=None):\n",
    "    if not head:\n",
    "        return None\n",
    "    if not head.next:\n",
    "        head.next = pre\n",
    "        return head\n",
    "    temp = head.next\n",
    "    head.next = pre\n",
    "    return reverse_list2(temp, head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([])\n",
    "mylist.head = reverse_list2(mylist.head)\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([1,2,3,4,5])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 4, 3, 2, 1]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.head = reverse_list2(mylist.head)\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 用递归实现，将head接在子链表的尾部\n",
    "def reverse_list3(head):\n",
    "    if not head:\n",
    "        return None\n",
    "    if not head.next:\n",
    "        return head\n",
    "    temp = head.next\n",
    "    head.next = None\n",
    "    sub_list = reverse_list3(temp)\n",
    "    temp.next = head\n",
    "    return sub_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([])\n",
    "mylist.head = reverse_list3(mylist.head)\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([1,2,3,4,5])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 4, 3, 2, 1]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.head = reverse_list3(mylist.head)\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 142. 环形链表 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。\n",
    "\n",
    "为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。\n",
    "\n",
    "说明：不允许修改给定的链表。\n",
    "\n",
    "\n",
    "示例 1：\n",
    "\n",
    "输入：head = [3,2,0,-4], pos = 1\n",
    "<img src=\"images/circularlinkedlist.png\">\n",
    "输出：tail connects to node index 1\n",
    "\n",
    "解释：链表中有一个环，其尾部连接到第二个节点。\n",
    "\n",
    "\n",
    "示例 2：\n",
    "\n",
    "输入：head = [1,2], pos = 0\n",
    "<img src=\"images/circularlinkedlist_test2.png\">\n",
    "输出：tail connects to node index 0\n",
    "\n",
    "解释：链表中有一个环，其尾部连接到第一个节点。\n",
    "\n",
    "\n",
    "示例 3：\n",
    "\n",
    "输入：head = [1], pos = -1\n",
    "<img src=\"images/circularlinkedlist_test3.png\">\n",
    "输出：no cycle\n",
    "\n",
    "解释：链表中没有环。\n",
    "\n",
    "\n",
    "进阶：\n",
    "你是否可以不用额外空间解决此题？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Floyd算法\n",
    "\n",
    "# 第一阶段，兔子一次走两步，乌龟一次走一步，兔子和乌龟同时从起点出发，找出相遇点\n",
    "def get_intersect(head):\n",
    "    tortoise = head\n",
    "    hare = head\n",
    "    \n",
    "    while hare and hare.next:\n",
    "        tortoise = tortoise.next\n",
    "        hare = hare.next.next\n",
    "        if tortoise == hare:\n",
    "            return tortoise\n",
    "    \n",
    "    return None\n",
    "\n",
    "# 第二阶段，两只乌龟，一个从起点出发，一个从相遇点出发，相遇点即为环的起点\n",
    "def detect_cycle(head):\n",
    "    intersect = get_intersect(head)\n",
    "    \n",
    "    if not intersect:\n",
    "        return -1\n",
    "    \n",
    "    pos = 0\n",
    "    p1 = head\n",
    "    p2 = intersect\n",
    "    while p1 != p2:\n",
    "        p1 = p1.next\n",
    "        p2 = p2.next\n",
    "        pos += 1\n",
    "    \n",
    "    return pos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 2, 0, -4]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([3,2,0,-4])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "node1 = mylist.get_node(1)\n",
    "node3 = mylist.get_node(3)\n",
    "node3.next = node1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "detect_cycle(mylist.head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "detect_cycle(mylist.head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([0])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "detect_cycle(mylist.head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([0])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "node0 = mylist.get_node(0)\n",
    "node0.next = node0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "detect_cycle(mylist.head)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 287. 寻找重复数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入: [1,3,4,2,2]\n",
    "输出: 2\n",
    "\n",
    "示例 2:\n",
    "\n",
    "输入: [3,1,3,4,2]\n",
    "输出: 3\n",
    "\n",
    "说明：\n",
    "\n",
    "不能更改原数组（假设数组是只读的）。\n",
    "只能使用额外的 O(1) 的空间。\n",
    "时间复杂度小于 O(n2) 。\n",
    "数组中只有一个重复的数字，但它可能不止重复出现一次。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 使用快慢指针找出环的入口，即为重复数字\n",
    "def find_duplicate(nums):\n",
    "    fast = 0\n",
    "    slow = 0\n",
    "    \n",
    "    while True:\n",
    "        fast = nums[nums[fast]]\n",
    "        slow = nums[slow]\n",
    "        if fast == slow:\n",
    "            break\n",
    "        \n",
    "    finder = 0\n",
    "    while True:\n",
    "        finder = nums[finder]\n",
    "        slow = nums[slow]\n",
    "        if finder == slow:\n",
    "            return finder"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_duplicate([1,3,4,2,2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_duplicate([3,1,3,4,2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 19. 删除链表的倒数第N个节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。\n",
    "\n",
    "示例：\n",
    "\n",
    "给定一个链表: 1->2->3->4->5, 和 n = 2.\n",
    "\n",
    "当删除了倒数第二个节点后，链表变为 1->2->3->5.\n",
    "\n",
    "说明：\n",
    "\n",
    "给定的 n 保证是有效的。\n",
    "\n",
    "进阶：\n",
    "\n",
    "你能尝试使用一趟扫描实现吗？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 一次遍历，使用间隔为n个节点的两个指针同步遍历\n",
    "def remove_nth_from_end(head, n):\n",
    "    fast = head\n",
    "    slow = head\n",
    "    \n",
    "    for i in range(n):\n",
    "        fast = fast.next\n",
    "    \n",
    "    if not fast:\n",
    "        return slow.next\n",
    "    \n",
    "    while fast.next:\n",
    "        fast = fast.next\n",
    "        slow = slow.next\n",
    "        \n",
    "    slow.next = slow.next.next\n",
    "    \n",
    "    return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([1,2,3,4,5])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 5]"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.head = remove_nth_from_end(mylist.head, 2)\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5]"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([1,2,3,4,5])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.head = remove_nth_from_end(mylist.head, 1)\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([1,2,3,4,5])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4, 5]"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.head = remove_nth_from_end(mylist.head, 5)\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1]"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([1])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.head = remove_nth_from_end(mylist.head, 1)\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 82. 删除排序链表中的重复元素 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入: 1->2->3->3->4->4->5\n",
    "输出: 1->2->5\n",
    "\n",
    "示例 2:\n",
    "\n",
    "输入: 1->1->1->2->3\n",
    "输出: 2->3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "def delete_duplicates(head):\n",
    "    dummy = ListNode(0)\n",
    "    dummy.next = head\n",
    "    x = dummy\n",
    "    while x and x.next:\n",
    "        while x.next and x.next.next and x.next.val == x.next.next.val:\n",
    "            while x.next.next and x.next.val == x.next.next.val:\n",
    "                x.next.next = x.next.next.next\n",
    "            x.next = x.next.next\n",
    "        x = x.next\n",
    "    return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 3, 4, 4, 5]"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([1,2,3,3,4,4,5])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 5]"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.head = delete_duplicates(mylist.head)\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 3, 4, 4, 5, 5]"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([1,2,3,3,4,4,5,5])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2]"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.head = delete_duplicates(mylist.head)\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 1, 2, 3, 3, 4, 4, 5, 5]"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([1,1,1,2,3,3,4,4,5,5])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2]"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.head = delete_duplicates(mylist.head)\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5]"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([1,1,1,2,2,3,3,4,4,5,5])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.head = delete_duplicates(mylist.head)\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1]"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([1,1])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.head = delete_duplicates(mylist.head)\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.head = delete_duplicates(mylist.head)\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 使用快指针和慢指针，快指针负责越过重复的数\n",
    "def delete_duplicates2(head):\n",
    "    dummy = ListNode(0)\n",
    "    dummy.next = head\n",
    "    fast = dummy.next\n",
    "    slow = dummy\n",
    "    while fast:\n",
    "        while fast.next and slow.next.val == fast.next.val:\n",
    "            fast = fast.next\n",
    "        if slow.next == fast:\n",
    "            slow = fast\n",
    "        else:\n",
    "            slow.next = fast.next\n",
    "        fast = fast.next\n",
    "    return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 3, 4, 4, 5]"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([1,2,3,3,4,4,5])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 3, 4, 4, 5]"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.head = delete_duplicates2(mylist.head)\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 3, 4, 4, 5, 5]"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([1,2,3,3,4,4,5,5])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 3, 4, 4, 5, 5]"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.head = delete_duplicates2(mylist.head)\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 1, 2, 3, 3, 4, 4, 5, 5]"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([1,1,1,2,3,3,4,4,5,5])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 1, 2, 3, 3, 4, 4, 5, 5]"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.head = delete_duplicates2(mylist.head)\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5]"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([1,1,1,2,2,3,3,4,4,5,5])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5]"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.head = delete_duplicates2(mylist.head)\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1]"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([1,1])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1]"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.head = delete_duplicates2(mylist.head)\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.head = delete_duplicates2(mylist.head)\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 203. 移除链表元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "删除链表中等于给定值 val 的所有节点。\n",
    "\n",
    "示例:\n",
    "\n",
    "输入: 1->2->6->3->4->5->6, val = 6\n",
    "\n",
    "输出: 1->2->3->4->5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 一次循环遍历\n",
    "def remove_elements(head, val):\n",
    "    x = head\n",
    "    last = None\n",
    "    while x:\n",
    "        if x.val == val:\n",
    "            if last:\n",
    "                last.next = x.next\n",
    "            else:\n",
    "                head = x.next\n",
    "        else:\n",
    "            last = x\n",
    "        x = x.next\n",
    "    return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 6, 3, 4, 5, 6]"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([1,2,6,3,4,5,6])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [],
   "source": [
    "mylist.head = remove_elements(mylist.head, 6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5]"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 1, 2, 6, 3, 4, 1, 5, 6]"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([1,1,1,2,6,3,4,1,5,6])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [],
   "source": [
    "mylist.head = remove_elements(mylist.head, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 6, 3, 4, 5, 6]"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [],
   "source": [
    "mylist.head = remove_elements(mylist.head, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 递归实现\n",
    "def remove_elements2(head, val):\n",
    "    if not head:\n",
    "        return None\n",
    "    head.next = remove_elements2(head.next, val)\n",
    "    if head.val == val:\n",
    "        return head.next\n",
    "    return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 6, 3, 4, 5, 6]"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([1,2,6,3,4,5,6])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [],
   "source": [
    "mylist.head = remove_elements2(mylist.head, 6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5]"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 1, 2, 6, 3, 4, 1, 5, 6]"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([1,1,1,2,6,3,4,1,5,6])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [],
   "source": [
    "mylist.head = remove_elements2(mylist.head, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 6, 3, 4, 5, 6]"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist = SinglyLinkedList()\n",
    "mylist.init_with_list([])\n",
    "mylist.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [],
   "source": [
    "mylist.head = remove_elements2(mylist.head, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.to_list()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3(py37)",
   "language": "python",
   "name": "py37"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
